import bisect
from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def minWastedSpace(self, packages: List[int], boxes_lst: List[List[int]]) -> int:
        packages.sort()

        # 计算前缀和
        prefix = [0]
        for package in packages:
            prefix.append((prefix[-1] + package) % MOD)

        ans = float("inf")

        for boxes in boxes_lst:
            boxes.sort()
            if packages[-1] > boxes[-1]:
                continue

            res = 0

            last = 0
            for box in boxes:
                now = bisect.bisect_right(packages, box)  # 寻找当前箱子需要处理的箱子
                res += box * (now - last) - (prefix[now] - prefix[last])
                last = now

            ans = min(ans, res)

            # print(packages, boxes, "->", res)

        if ans == float("inf"):
            return -1
        else:
            return ans % MOD


if __name__ == "__main__":
    print(Solution().minWastedSpace(packages=[2, 3, 5], boxes_lst=[[4, 8], [2, 8]]))  # 6
    print(Solution().minWastedSpace(packages=[2, 3, 5], boxes_lst=[[1, 4], [2, 3], [3, 4]]))  # -1
    print(Solution().minWastedSpace(packages=[3, 5, 8, 10, 11, 12], boxes_lst=[[12], [11, 9], [10, 5, 14]]))  # 9
